package com.datastructures2.graph.最短路径;


import com.datastructures2.tree2.IndexMinPQ;
import com.datastructures2.背包队列栈.Stack;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

/**
 * 最短路径的Dijkstra算法
 * @author MaoLin Wang
 * @date 2020/2/2412:16
 */
public class DijkstraSP {
    private DirectedEdge[] edgeTo;
    private  double[] distTo;
    /**
     * 索引优先队列：顶点v作为索引，从起点到v的最短路径的权值作为索引关联的对象
     */
    private IndexMinPQ<Double> pq;

    public DijkstraSP(EdgeWeightedDigraph digraph,int s){
        for (DirectedEdge e : digraph.edges()) {
            if (e.weight() < 0)
                throw new IllegalArgumentException("边 " + e + " 的权重为负值！");
        }
        edgeTo=new DirectedEdge[digraph.V()];
        distTo=new double[digraph.V()];
        pq=new IndexMinPQ<>(digraph.V());

        //初始化为无穷大
        for (int v = 0; v < digraph.V(); v++) {
            distTo[v]=Double.POSITIVE_INFINITY;
        }

        distTo[s]=0;

        pq.insert(s,0.0);
        while (!pq.isEmpty()){
            relax(digraph,pq.delMin());
        }
    }

    /**
     * 对顶点v的邻边放松
     * @param digraph
     * @param v
     */
    private void relax(EdgeWeightedDigraph digraph, int v) {
        for (DirectedEdge edge:digraph.adj(v)){
            int to=edge.to();

            if (distTo[to]>distTo[v]+edge.weight()){
                distTo[to]=distTo[v]+edge.weight();
                edgeTo[to]=edge;
                if (pq.contains(to)){
                    pq.changeKey(to,distTo[to]);
                }else {
                    pq.insert(to,distTo[to]);
                }
            }
        }
    }

    /**
     * 从起点到顶点v的最短路径权值
     * @param v
     * @return
     */
    public double distTo(int v){
        return distTo[v];
    }

    /**
     * 是否存在从s到v的最短路径
     * @param v
     * @return
     */
    public boolean hasPathTo(int v){
        return distTo[v]<Double.POSITIVE_INFINITY;
    }

    /**
     * 返回从s到v的最短路径
     * @param v
     * @return
     */
    public Iterable<DirectedEdge> pathTo(int v){
        if (!hasPathTo(v))return null;
        Stack<DirectedEdge> path=new Stack<>();
        for (DirectedEdge edge=edgeTo[v];edge!=null;edge=edgeTo[edge.from()])
        {
            path.push(edge);
        }
        return path;
    }
    public static void main(String[] args) {
        In in = new In("D:\\JavaProject\\算法\\数据结构和算法\\DATAStructures\\alg\\src\\main\\java\\com\\datastructures2\\graph\\最小生成树\\tinyEWG.txt");
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);

        // compute shortest paths
        DijkstraSP sp = new DijkstraSP(G, 3);


        // print shortest path
        for (int t = 0; t < G.V(); t++) {
            if (sp.hasPathTo(t)) {
                StdOut.printf("%d to %d (%.2f)  ", 3, t, sp.distTo(t));
                for (DirectedEdge e : sp.pathTo(t)) {
                    StdOut.print(e + "   ");
                }
                StdOut.println();
            }
            else {
                StdOut.printf("%d to %d         no path\n", 0, t);
            }
        }
    }
}
